package main

import "fmt"

func generateParenthesis(n int) []string {
	var paths []string
	var parenthHelper func(int, int, string)
	parenthHelper = func(left, right int, path string) {
		if right == 0 {
			paths = append(paths, path)
			return
		}
		if left == right {
			parenthHelper(left-1, right, path+"(")
			return
		}
		if left > 0 {
			parenthHelper(left-1, right, path+"(")
			parenthHelper(left, right-1, path+")")
		} else if left == 0 {
			parenthHelper(left, right-1, path+")")
		}

	}
	parenthHelper(n, n, "")
	return paths
}

func main() {
	fmt.Println(generateParenthesis(1))
}
